The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Additionally, one or more security operations are typically performed on each packet. But before these operations can be performed, a packet classification operation must typically be performed on the packet.
Packet classification as required for, inter alia, access control lists (ACLs) and forwarding decisions, is a demanding part of switch and router design. The packet classification of a received packet is increasingly becoming more difficult due to ever increasing packet rates and number of packet classifications. For example, ACLs require matching packets on a subset of fields of the packet flow label, with the semantics of a sequential search through the ACL rules. IP forwarding requires a longest prefix match.
Known approaches of packet classification include using custom application-specific integrated circuits (ASICs), custom circuitry, software or firmware controlled processors, binary and ternary content-addressable memories (CAMs). The use of programmable software or firmware have advantages as they provide some level of flexibility, which becomes especially important as new protocols and services are added to existing network. Customer typically desire to use their existing hardware (e.g., routers, switches, etc.) to support these new protocols and services. However, known software and firmware implementations are relatively slow, and typically place a performance bound which may be incompatible with new requirements. Various applications that use packet classification, such as Security Access Control, Quality of Service, etc., typically need to perform many matches on source and destination port numbers, protocol and/or other header fields, etc. in order to identify a corresponding netflow.
In a known prior system, one or more fields are extracted from a received packet. These one or more extracted fields typically include source and destination addresses, port numbers, and possibly other fields, typically included in the header or flow label of a packet. These extracted fields are provided in their native format, possibly along with other data, to a CAM, which performs a lookup operation in performing the packet classification. Because CAMs are expensive, especially in terms of space and power consumption and are limited in the width of an input lookup word, one known system preprocesses, via one or more logical functions or operations, certain information contained in a packet to generate a vector that is used as part of a lookup word. This vector reduces the number of bits that would be required if the entire native information was included in the lookup word. Bechtolsheim et al. U.S. Pat. 6,377,577, inter alia, discloses a system that includes preprocessing circuitry for generating packet labels for use in lookup operations. When controlling access for packets responsive to their input interfaces, the packet label includes an identifier for the input interface. When controlling access for packets responsive to their output interfaces, the packet label includes an identifier for the output interface. Ross et al., U.S. Pat. No. 6,658,002, inter alia, discloses a system that associates an interface number corresponding to the input interface on which an inbound packet was received or the output interface for an outbound packet, with this interface number being mapped into an ACL label. The ACL label can then be used in identifying how to process the inbound or outbound packet, such as the ACL label being included as part of the flow label in a lookup word, and the ACL being used to select additional information to add to the lookup word.
Programming an ACL can be a complex and/or redundant task. Typically, each network or possibly even host system requires a separate series of ACL entries. One known system reduces the overall numbers of ACLs by assigning virtual local area network (VLAN) identifiers to entities (e.g., networks, hosts, and router interfaces). A common ACL can then be shared by multiple entities by mapping their VLAN identifiers to a shared VLAN label, with this shared VLAN label being used to identify the common ACL or entries thereof.
However, in many situations, ACLs used on different interfaces are not the same as, for example, they might have different security requirements. Also, different interfaces may belong to different subnets and use different IP addresses; and thus, for example, separate ACLs entries must be used to verify that the source address of a packet sent from an interface matches the address of the interface. This creates a difficulty especially in the case of a dial-in public network, where the connecting computer and user varies, and the only mechanism currently available to ensure that a packet sent from the connected computer is authorized (e.g., its source address corresponds to the one assigned to it by the dial-in system), is to use a separate ACL for each interface, which can be quite tenuous and expensive as each ACL must be programmed separately. Needed are new methods and apparatus for, inter alia, allowing sharing of an ACL for additional operations and/or functionality.